package com.cfc.stage1;

import common.ListNode;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * @description: 环形链表
 *  https://leetcode.cn/problems/linked-list-cycle/description/
 * @author: yangxuan10
 * @create: 2024-04-23 09:59
 **/
public class HasCycle {

    @Test
    public void test1() {
        ListNode listNode1 = ListNode.arrayConversionListNode("12345");
        System.out.println(hasCycle(listNode1));
    }

    /**
         假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。
         当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，
         那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会
         先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于
         「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

         我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一慢。
         慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，
         而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来
         追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表
         不为环形链表。
     */
    public boolean hasCycle3(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
/*        兔子会不会「跳过」乌龟，从来不会和乌龟相遇呢？
        这是不可能的。如果有环的话，那么兔子和乌龟都会进入环中。
        这时用「相对速度」思考，乌龟不动，兔子相对乌龟每次只走一步，这样就可以看出兔子一定会和乌龟相遇了。*/
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    public boolean hasCycle2(ListNode head){
        if (head == null || head.next == null) {
            return false;
        }
        //兔子在第二个节点上 开始跑呢
        ListNode tuzi = head.next;
        while (true) {
            if (tuzi == null || tuzi.next == null) {
               break;
            }
            tuzi = tuzi.next;
            if (tuzi == head) {
                return true;
            }
            tuzi = tuzi.next;
            if (tuzi == head) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

    /**
     * 哈希表
     */
    public boolean hasCycle1(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }


    /**
     * 原创：
     * 这个算法我们走了巧劲了，是不合理了啊...并且还改变了原来的值。
     *   -10^5 <= Node.val <= 10^5
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        int a = 100002;
        ListNode current = head;
        while (current != null) {
            if (a == current.val) {
                return true;
            }
            current.val = a;
            current = current.next;
        }
        return false;
    }

}